A technology to store data to a storage after compressing the data is known in information processing systems such as storage devices including a storage. With the technology, a data amount stored in the storage can be reduced and use efficiency of the storage can be enhanced.
An example of a data compression algorithm includes a dictionary compression algorithm. The dictionary compression algorithm is a compression algorithm to assign a code to a unique data string that has once appeared, and record the code and a match length for the same data string that appears afterward.
By the way, a storage device, i.e., a block storage, which controls input/output of data to/from a storage in block, is known. In the block storage, the data is compressed in units of input/output (in block), for example.
As described above, the dictionary compression algorithm is performed on the assumption of existence of the data string that appears a plurality of times, in the data to be compressed. Therefore, when compression processing is individually performed for each block, the frequency of appearance of the same data string in the block becomes lower as the size per block becomes smaller, and a high compression ratio may not be expected.
Therefore, technologies to improve the compression ratio by compressing a plurality of blocks by overall compression are known.    Patent Document 1: Japanese National Publication of International Patent Application No. 2016-524821    Patent Document 2: Japanese Laid-open Patent Publication No. 2011-48679    Non-Patent Document 1: EMC Corporation, “INTRODUCTION TO THE EMC XtremIO STORAGE ARRAY (Ver. 4.0) A Detailed Review”, White Paper, [online], May 2015, [searched on Oct. 14, 2016], the Internet <URL://japan.emc.com/collateral/white-papers/h11752-intro-to-XtremIO-array-wp.pdf>
When a read access from a host device to the storage occurs, the storage device which compresses and stores data decompresses and stores a portion from a head to a tail of data to be read out, of compressed data, and responds to the host with the data to be read out obtained through the decompression. The reason to perform decompression processing from the head of the compressed data is because the decompression processing depends on data prior to the processing portion in the compressed data, and thus the decompression processing is not able to be started from a middle of the compressed data.
Therefore, in a case of overall compression of a plurality of blocks, when read-out of a portion (block) other than the head block in the compressed data (hereinafter, the read-out is written as “partial read-out”) occurs, the decompression processing may take longer time than that in a case of compression in block.
As described above, it is effective to increase the number of blocks to be compressed by overall compression in order to increase the compression ratio. However, the frequency of occurrence of the partial read-out becomes higher as the number of blocks to be compressed by overall compression is larger, and thus a possibility to decrease read access performance becomes high.